#include <iostream>
#include <vector>

using namespace std;
// 4. 寻找两个正序数组的中位数
// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
// https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

class Solution {
private:
    int mid, mid1, mid2;    // 存放中位数
    // 已知数组的大小为n，归并次数为k，当前处理的元素为x。判断是否为中位数
    bool findmid(size_t n, int k, int x) {
        if(n % 2 == 1) {    // 总元素个数为奇数
            if(k == n / 2) {
                mid = x;    // 求出唯一的中位数
                return true;    // 返回true
            }
        } else {    // 总元素个数为偶数
            if(k == n/2 - 1)    // 找到第1个中位数
                mid1 = x;
            else if(k == n/2)   // 找到第2个中位数
            {
                mid2 = x;
                return true;    // 两个中位数都求出后返回true
            }
        }
        return false;   // 其他情况返回 false
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        size_t nums1Size = nums1.size();
        size_t nums2Size = nums2.size();
        size_t n = nums1Size +nums2Size;    // 总的元素个数
        int i = 0, j = 0, k = 0;    // nums1的游标i，nums2的游标j，归并次数k
        bool flag = false;  // 表示中位数是否已经求出
        // 二路归并
        while(i < nums1Size && j < nums2Size) {
            if(nums1[i] < nums2[j]) {   // 归并 nums1[i]
                flag = findmid(n, k, nums1[i]);
                if(flag) break; // 求出中位数后退出循环
                i++;
            } else {
                flag = findmid(n, k, nums2[j]);
                if(flag) break;
                j++;
            }
            k++;    // 归并次数加1
        }

        while(i < nums1Size && !flag) {
            flag = findmid(n,k,nums1[i]);
            k++;
            i++;
        }
        while(j < nums2Size && !flag) {
            flag = findmid(n, k, nums2[j]);
            k++;
            j++;
        }

        if(n % 2 == 1)
            return mid;
        else
            return (1.0 * mid1 + mid2) / 2;
    }
};

int main() {
    vector<int> nums11 = {1, 3};
    vector<int> nums12 = {2};
    cout << Solution().findMedianSortedArrays(nums11, nums12) << endl;
    // 2

    vector<int> nums21 = {1, 2};
    vector<int> nums22 = {3, 4};
    cout << Solution().findMedianSortedArrays(nums21, nums22) << endl;
    // 2.5

    vector<int> nums31 = {};
    vector<int> nums32 = {1};
    cout << Solution().findMedianSortedArrays(nums31, nums32) << endl;
    // 1
    return 0;
}
